package com.kizuki.algorithm.leetcode;

import java.util.Stack;

/**
 * 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
 * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
 *
 *
 */
public class _132模式 {

    class Solution {
        public boolean find132pattern(int[] nums) {
            Stack<Integer> stack = new Stack<>();
            int K = Integer.MIN_VALUE;
            int len = nums.length;
            for(int i = len - 1; i >= 0; i--) {
                if (K > nums[i])  return true;
                while(!stack.isEmpty() && stack.peek() < nums[i]) {
                    K = stack.pop();
                }
                stack.push(nums[i]);
            }
            return false;
        }
    }
}
